package algorithm.linetable.array;

import java.util.HashSet;
//重点是hashset的contain方法使用
//get新起点

public class LongestConsecutiveSequence {
    // Longest Consecutive Sequence
// Time Complexity: O(n)，Space Complexity: O(n)
        public int longestConsecutive(int[] nums) {
            final HashSet<Integer> mySet = new HashSet<Integer>();
            for (int i : nums) mySet.add(i);
            int longest = 0;
            for (int i : nums) {
                int length = 1;
                for (int j = i - 1; mySet.contains(j); --j) {
                    mySet.remove(j);
                    ++length;
                }
                for (int j = i + 1; mySet.contains(j); ++j) {
                    mySet.remove(j);
                    ++length;
                }
                longest = Math.max(longest, length);
            }
            return longest;
        }


    public static void main(String[] args) {
        LongestConsecutiveSequence lcs = new LongestConsecutiveSequence();
        int[] nums = {100,4,200,1,3,2,7,9,8,10,11,1};
/*        for(int i:nums){
            System.out.print(" "+i);
        }*/
        int length = lcs.longestConsecutive(nums);
        System.out.println(length);
    }
}
